BZOJ1860【ZJOI2006】Mahjong麻将 < DP >

Problem

【ZJOI2006】Mahjong麻将

Description

很多人都知道玩麻将，当然也有人不知道，呵呵，不要紧，我在这里简要地介绍一下麻将规则：
普通麻将有砣、索、万三种类型的牌，每种牌有个数字，其中相同的牌每个有四张，例如，，各张，所以共张牌。胡牌时每人有张牌，其中只要某人手里有若干句话（就是同种类型的牌连续三张或同种牌三张），另外再加上一对，即可胡牌。当然如果全是对，叫七小对，也可以胡牌。
要判断某人是否胡牌，显然一个弱智的算法就行了，某中学信息学小组超级麻将迷想了想，决定将普通麻将改造成超级麻将。
所谓超级麻将没有了砣、索、万的区分，每种牌上的数字可以是而每种数字的牌各有张。另外特别自由的是，玩牌的人手里想拿多少张牌都可以，好刺激哦！
刺激归刺激，但是拿多了怎么胡牌呢？
超级麻将规定只要一个人手里拿的牌是若干句话（三个连续数字的牌各一张组成一句话，三张或四张同样数字的牌也算一句话），再加上一对相同的牌，就算胡了。
作为信息学竞赛选手的你，麻烦你给这位超级麻将迷编个程序，判断能否胡牌。

Input

第一行一个整数（），表示玩了次超级麻将。接下来行，每行个数，描述每次玩牌手中各种牌的数量。表示数字为的牌有张。（）

Output

输出行，若胡了则输出，否则输出，注意区分、的大小写！

Sample Input

3
2 4 0 0 0 0 0 …… 0（一共98个0）
2 4 2 0 0 0 0 …… 0（一共97个0）
2 3 2 0 0 0 0 …… 0（一共97个0）

Sample Output

1
2
3

Yes
Yes
No

标签：DP

Solution

一道比较常规的。
记得另外一道省选麻将题可以贪心做，但此题不行，没有贪心策略。
考虑动态规划。发现一个数的牌数只可能影响它前后三个连续数的牌数（毕竟顺子只能三个连续），设表示把前中数字取完，取完之前数字为的共张，为的共张，表示是否取了对子，能否有取法。那么根据不同情况，可以从取二对子、三对子、四对子、顺子的情况转移过来。
除了方程特判有点多，还是挺好写的。

Code

#include <bits/stdc++.h>
using namespace std;
int a[105];	bool f[105][105][105][2];
int main() {
    int T;	scanf("%d", &T);
    while (T--) {
        memset(f, false, sizeof f), f[0][0][0][0] = true;
        for (int i = 1; i <= 100; i++)	scanf("%d", a+i);
        for (int i = 1; i <= 100; i++)
            for (int j = 0; j <= a[i-1]; j++)
                for (int k = 0; k <= a[i]; k++) {
                    if (k >= 2)	f[i][j][k][1] |= f[i][j][k-2][0];
                    if (k >= 3)	f[i][j][k][0] |= f[i][j][k-3][0];
                    if (k >= 3)	f[i][j][k][1] |= f[i][j][k-3][1];
                    if (k >= 4)	f[i][j][k][0] |= f[i][j][k-4][0];
                    if (k >= 4)	f[i][j][k][1] |= f[i][j][k-4][1];
                    if (j >= k && a[i-2] >= k)	f[i][j][k][0] |= f[i-1][(i >= 2 ? a[i-2] : 0)-k][j-k][0];
                    if (j >= k && a[i-2] >= k)	f[i][j][k][1] |= f[i-1][(i >= 2 ? a[i-2] : 0)-k][j-k][1];
                }
        printf("%s\n", f[100][a[99]][a[100]][1] ? "Yes" : "No");
    }
    return 0;
}